package problems.practice;

/**
 * 135. 分发糖果
 * <p>https://leetcode.cn/problems/candy/</p>
 *
 * @author habitplus
 * @since 14:07, 2022/10/3
 */
public class T135 {
    public int candy(int[] ratings) {
        int n = ratings.length;

        // dp[i] 表示从 ratings[i+1] 开始，连续严格递减的序列的长度
        int[] right = new int[n];
        for (int i = n - 2; i >= 0; --i) {
            if (ratings[i] > ratings[i + 1]) right[i] = right[i + 1] + 1;
        }

        // ratings[i] 左边连续递增序列的长度
        int left = 0;
        int ret = 0;

        for (int i = 0; i < n; ++i) {
            if (i > 0) {
                if (ratings[i] > ratings[i - 1]) {
                    ++left;
                } else {
                    left = 0;
                }
            }

            ret += Math.max(right[i], left) + 1;
        }

        return ret;
    }
}
